package com.hanxiaozhang.no10leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 〈一句话功能简述〉<br>
 * 〈通过中序和后序遍历重建一棵二叉树〉
 * 实例 1:
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 * 示例 2:
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 * <p>
 * 思路：见方法1注释
 *
 * @author hanxinghua
 * @create 2024/4/11
 * @since 1.0.0
 */
public class No106ConstructByInorderAndPostorderTraversal {


    public static void main(String[] args) {

        int[] inOrder = {9, 3, 15, 20, 7};
        int[] postOrder = {9, 15, 7, 20, 3};

        TreeNode tree = method1(inOrder, postOrder);

        System.out.println();


    }


    /**
     * 方法1（递归形式）
     * 后序遍历形式：
     * [[左子树的后序遍历结果], [右子树的后序遍历结果], 根节点]，即根节点总是后序遍历中的第一个节点。
     * 中序遍历的形式：
     * [[左子树的中序遍历结果], 根节点, [右子树的中序遍历结果]]
     * 推论：
     * 1.在中序遍历中，定位到根节点，我们就可以分别知道左子树和右子树中的节点数目。
     * 2.后序遍历和中序遍历的长度是相同的，因此，可以在对应的前序遍历结果中，对上述形式中的所有左右括号进行定位。
     *
     * @param inOrder
     * @param postOrder
     * @return
     */
    private static TreeNode method1(int[] inOrder, int[] postOrder) {

        int n = inOrder.length;

        Map<Integer, Integer> inIndexMap = new HashMap();
        for (int i = 0; i < n; i++) {
            inIndexMap.put(inOrder[i], i);
        }

        return recursion(postOrder, inIndexMap, 0, n - 1, 0, n - 1);

    }

    public static TreeNode recursion(int[] postOrder, Map<Integer, Integer> inIndexMap, int postLeftIndex, int postRightIndex, int inLeftIndex, int inRightIndex) {

        if (postLeftIndex > postRightIndex) {
            return null;
        }

        int postRootIndex = postRightIndex;

        int inRootIndex = inIndexMap.get(postOrder[postRootIndex]);

        TreeNode root = new TreeNode(postOrder[postRootIndex]);

        int subRightTreeSize = inRightIndex - inRootIndex;

        // 后序遍历： [[左子树的后序遍历结果], [右子树的后序遍历结果], 根节点]
        // 中序遍历：[[左子树的中序遍历结果], 根节点, [右子树的中序遍历结果]]

        // 递归地构造左子树，并连接到根节点
        // -- 后序遍历中「 左边界 , 右边界 -1- subLeftTreeSize」的元素 对应 中序遍历中「左边界 , 根节点-1」的元素
        root.left = recursion(postOrder, inIndexMap, postLeftIndex, postRightIndex - 1 - subRightTreeSize, inLeftIndex, inRootIndex - 1);

        // 递归地构造右子树，并连接到根节点
        // -- 后序遍历中「 右边界 - subRightTreeSize  , 右边界-1」的元素  对应  中序遍历中「根节点 + 1 到 右边界」的元素
        root.right = recursion(postOrder, inIndexMap, postRootIndex - subRightTreeSize, postRootIndex - 1, inRootIndex + 1, inRightIndex);

        return root;
    }

}
